﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace KnightShortestPath
{
    /// <summary>
    /// This class is the controller of the game, and allows to set up the initial parameters of the simulation; those parameters are
    /// the initial position for knight and queen. This class also contains an instance of the <see cref="KnightShortestPath.Tree"/> 
    /// class to find out the shortest path between knight and queen, and an instance of the <see cref="KnightShortestPath.Knight"/> 
    /// class to calculate the possible movements of the knight.
    /// </summary>
    public class GameController
    {
        /// <summary>
        /// Instance of the <see cref="KnightShortestPath.Knight"/> class that allows to calculate the possible next movements of the knight
        /// </summary>
        private Knight knight;
        
        /// <summary>
        /// Instance of the <see cref="KnightShortestPath.Tree"/> class that allows to obtain the tree of possible movements of the knight
        /// </summary>
        private Tree gameTree;
        
        /// <summary>
        /// Instance of the <see cref="KnightShortestPath.Node"/> class that represents the initial position of the knight
        /// </summary>
        private Node knightPosition;

        /// <summary>
        /// Instance of the <see cref="KnightShortestPath.Node"/> class that represents the position of the queen 
        /// </summary>
        private Node queenPosition;

        /// <summary>
        /// List of instances of the <see cref="KnightShortestPath.Node"/> class that contais all possible shortest paths, 
        /// that is, all paths which their number of steps is the minimun possible
        /// </summary>
        private List<Node>[] shortestPaths;

        /// <summary>
        /// Matrix that allows to know which positions on the chessboard has been already occupied
        /// </summary>
        private bool[,] positionMarked;

        /// <summary>
        /// Number of steps for the shorest path.
        /// </summary>
        private int stepsInShortestPath;

        /// <summary>
        /// Creates a new instance of the <see cref="KnightShortestPath.GameController"/> class.
        /// </summary>
        /// <param name="knightPosition">
        /// KnightPosition: Instance of the <see cref="KnightShortestPath.Node"/> class that represents 
        /// the initial position of the knight
        /// </param>
        /// <param name="queenPosition">
        /// QueenPosition: Instance of the <see cref="KnightShortestPath.Node"/> class that represents 
        /// the position of the queen
        /// </param>
        public GameController(Node knightPosition, Node queenPosition)
        {
            this.knightPosition = knightPosition;
            this.queenPosition = queenPosition;
            this.knight = new Knight(knightPosition);
            this.gameTree = new Tree(knightPosition);
            this.shortestPaths = null;
            this.positionMarked = new bool[8, 8];
        }

        /// <summary>
        /// Creates a new instance of the <see cref="KnightShortestPath.GameController"/> class.
        /// </summary>
        public GameController() : this(new Node(0, 0), new Node(7, 7)) { }

        /// <summary>
        ///  StepsInShortestPath Property: Gets the value of steps in the shortest path.
        /// </summary>
        public int StepsInShortestPath
        {
            get { return stepsInShortestPath; }
        }

        /// <summary>
        /// Paths Property: Gets all possibles shortest paths.
        /// </summary>
        public List<Node>[] Paths
        {
            get { return shortestPaths; }
        }

        /// <summary>
        /// KnightPosition Property: Gets the knight's position.
        /// </summary>
        public Node KnightPosition
        {
            get { return knightPosition; }
        }

        /// <summary>
        /// QueenPosition Property: Gets the queen's Position.
        /// </summary>
        public Node QueenPosition
        {
            get { return queenPosition; }
        }

        /// <summary>
        /// NumberOfMovements Property: Gets the total number of movements required to find the shortest path.
        /// </summary>
        public long NumberOfMovements
        {
            get { return this.gameTree.NodesNumber(); }
        }

        /// <summary>
        /// Starts the processing to find the shortest path between the knight and the queen according to 
        /// their current positions
        /// </summary>
        public void startProcessing() {
            this.AddMovement(knightPosition);
            this.shortestPaths = this.ShortestPaths();
        }

        /// <summary>
        /// Completes the tree of movements with all possible options for the knight to move
        /// </summary>
        /// <param name="knightPosition">
        /// Knight Position: Instance of the <see cref="KnightShortestPath.Node"/> class that 
        /// represents the current position of the knight
        /// </param>
        private void AddMovement(Node knightPosition) 
        {
            if (!this.IsFinalPosition(knightPosition))
            {
                this.knight.Position = knightPosition;
                Node[] move = this.knight.NextMovement;
                this.positionMarked[knightPosition.Row, knightPosition.Col] = true;

                // Adds to the tree all possibles movement of the knight in their respectiveble position (index)
                for (int i = 0; i < move.GetLength(0); i++)
                {
                    if (move[i] != null)
                    {
                        gameTree.AddNode(knightPosition, i, move[i]);
                    }
                    
                }

                // If in the array of movements there is the final position, there's no need to keep looking for
                // another possibles solutions in this branch, because it's about looking for the shortest path
                if (!this.HasFinalPosition(move))
                {

                    for (int i = 0; i < move.GetLength(0); i++)
                    {
                        if(move[i] != null){
                            // Evaluates if the knight has already pass through the current position, if it is so then 
                            // look if the parent node is the same and generate a "cloned" branch to avoid keep looking 
                            // for a path that has already been found
                            if (!this.IsPreviousMovement(move[i]))
                            {
                                this.AddMovement(move[i]);
                            }
                            else
                            {
                                if (!this.gameTree.IsAncestor(knightPosition, move[i]))
                                {
                                    Node branch = this.gameTree.CloneTree(move[i]);
                                    this.gameTree.AddNode(knightPosition, i, branch);
                                }
                            }
                        }                        
                    }
                }
            }
        }

        /// <summary>
        /// Finds all path which the number of steps of the knight are the minimun possible 
        /// to reach the position of the queen
        /// </summary>
        /// <returns>
        /// Returns a list of instances of the <see cref="KnightShortestPath.Node"/> class that contais all possible 
        /// shortest paths, that is, all paths which their number of steps is the minimun possible
        /// </returns>
        private List<Node>[] ShortestPaths() 
        {
            // Obteins an array of all branches of the tree that contains the position of the queen
            Node[] found = this.gameTree.FindAllNodes(queenPosition).ToArray();
            List<Node>[] shortestPaths = null;
            if (found.GetLength(0) < 1) {
                return null;
            }

            // If there's any path between the knight and the queen, then finds the shortest possible
            int[] steps = new int[found.GetLength(0)];
            int lowestIndex = steps.GetLength(0);
            int lowestValue = Int16.MaxValue;

            for (int i = 0; i < steps.GetLength(0); i++){
                steps[i] = this.gameTree.LevelsNumber(found[i]);
                if(steps[i] < lowestValue){
                    lowestValue = steps[i];
                    lowestIndex = i;
                }
            }

            // obtains the number of steps in the shortest path
            this.stepsInShortestPath = lowestValue - 1;

            if (found.GetLength(0) > 1)
            {
                // Looks for the index of all paths which its number of steps is the lowest and
                // add them to the list of possible paths
                List<int> possiblePathsIndex = new List<int>();
                for (int i = 0; i < steps.GetLength(0); i++)
                {
                    if (steps[i] == lowestValue)
                    {
                        possiblePathsIndex.Add(i);
                    }
                }

                // Finds the whole path for each possible shortest path according to the 
                // list of the possible paths index
                shortestPaths = new List<Node>[possiblePathsIndex.Count];
                for (int i = 0; i < possiblePathsIndex.Count(); i++ )
                {
                    int index = possiblePathsIndex.ElementAt(i);
                    Node pathEnd = found[index];
                    shortestPaths[i] = this.gameTree.FindAncestorsLine(pathEnd);
                }
            }
            else 
            {
                // If there is only one shortest path creates a list of one element
                shortestPaths = new List<Node>[1];
                Node pathEnd = found[lowestIndex];
                shortestPaths[0] = this.gameTree.FindAncestorsLine(pathEnd);
            }

            return shortestPaths;
        }

        /// <summary>
        /// Validates if a specific position is equivalent to queen's position
        /// </summary>
        /// <param name="currentPosition">
        /// Current Position: An instance of the <see cref="KnightShortestPath.Node"/> class that represents a specific 
        /// position on the chessboard
        /// </param>
        /// <returns>
        /// True if the current position is equivalent to queen's position, otherwise, False
        /// </returns>
        private bool IsFinalPosition(Node currentPosition)
        {
            return this.queenPosition.Equivalent(currentPosition);
        }

        /// <summary>
        /// Validates if a specific position has already been occupied
        /// </summary>
        /// <param name="position">
        /// Position: Instance of the <see cref="KnightShortestPath.Node"/> class that represents a specific 
        /// position on the chessboard
        /// </param>
        /// <returns>
        /// True if the position has already been occupied, otherwise, False
        /// </returns>
        private bool IsPreviousMovement(Node position)
        {
            return this.positionMarked[position.Row, position.Col];
        }

        /// <summary>
        /// Validates if at less one of the positions in an array of movements is equivalent 
        /// to the queen's possition
        /// </summary>
        /// <param name="move">
        /// Move: Array of instances of the <see cref="KnightShortestPath.Node"/> class that represent 
        /// movements on the chessboard
        /// </param>
        /// <returns>
        /// True if there is any position in the array equivalent to the queen's position, otherwise, False
        /// </returns>
        private bool HasFinalPosition(Node[] move)
        {
            bool hasFinal = false;
            foreach (Node n in move) {
                hasFinal |= this.IsFinalPosition(n);
            }
            return hasFinal;
        }

    }
}
